import javax.lang.model.util.Elements;

public class Sort {
    /**
     * 直接插入排序
     * 具有稳定性
     * 时间复杂度为：最好情况下：计算时间复杂度的时候计算执行次数最多的语句类
     * 最好情况下O(n) ,最坏情况下O(n^2)
     * 空间复杂度为：O(1);
     */
    public void insertSort(int[] array) {
        //直接插入排序
        //思想：前面的数据看作有序的，依次遍历后面的数据群，将其插入到前面的数据群中去，使得前面的数据群变为有序
        //当所有的乱序元素遍历完时，整个数组直接插入排序完成。
        for (int i = 1; i < array.length; i++) {
            //比较乱序数组的第一个元素与有序数组的每个元素，直到下标为0为止。
            int tmp = array[i];
            //指向乱序的数组下标与指向有序数组下标是有关联的，所以用一个变量表示即可
            int j = i - 1;
            for (; j >= 0; j--) {
                //当数组改变时，其对应下标的值也会改变
                //当乱序的元素比有序的元素的值小时
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                    //此时还需判断一下
                 /*   if(j ==0){
                        array[j] =tmp;
                        sortend++;
                    }*/
                } else {
                    array[j + 1] = tmp;
                    break;
                }
            }
            //当执行到此时,j 是0还是-1？是   - 1
            //当乱序的元素插入到有序元素的中间时，这条语句的执行会不会出现错误？
            //此种情况下j不为-1.
            array[j + 1] = tmp;

        }
    }

    /**
     * 希尔排序
     */
    public void shellsort(int[] array) {
        //希尔排序
        //将每次分组后的数据进行调整，根据gap进行分组
        for (int gap = array.length / 2; gap >= 1; gap = gap / 2) {
            //当gap ==1时，每一个元素会不会与前面的元素进行比较？
            //当某一个元素在两个分组中，自
            shell(array, gap);
        }
    }

    private void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            //比较乱序数组的第一个元素与有序数组的每个元素，直到下标为0为止。
            int tmp = array[i];
            //指向乱序的数组下标与指向有序数组下标是有关联的，所以用一个变量表示即可
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                //当数组改变时，其对应下标的值也会改变
                //当乱序的元素比有序的元素的值小时
                if (tmp < array[j]) {
                    array[j + gap] = array[j];
                } else {
                    array[j + gap] = tmp;
                    break;
                }
            }

            array[j + gap] = tmp;

        }


    }
    /**
     *  选择排序1
     *  问题1：进行选择排序应该遍历多少次。
     *  问题2：遍历的次数序号与单次遍历中起始位置的数值关系
     *
     *
     *
     */
public void  selectSort1(int[] array) {
    //每次挑选出一个最小的数据，放在小下标处
    for (int k = 0; k < array.length-1; k++) {
       // 不存储数据，存储下标
        int tmp =k;
        for (int i = k+1; i < array.length; i++) {
            if (array[i] < array[tmp]) {
                 tmp = i;
            }
        }
              swap(array,tmp,k);
    }
}
private void swap(int[] array,int x,int y){
      int tmp = array[x];
      array[x] =array[y];
      array[y] =tmp;
}

    /**
     * 选择排序2：
     *  思想：对第一个选择排序思想的优化，上一个思想只是在一端开始进行放置有序数据
     *  可以在两端分别放置最大与最小的数据
     *
     * @param array
     */
    public void selectsort2(int []array){
        int left = 0;
        int right = array.length-1;
        while (left<right){
            int minIndex = left;
            int maxIndex = right;
            //问题，怎样获取最大值与最小值？
            //遍历中间区间，逐渐获取小与大的数据
            for (int i = left; i <=right ; i++) {  //漏：如果left下标的值为最大值呢？
                  if(array[i]<array[minIndex]){
                        minIndex = i ;
                  }
                  if(array[i]>array[maxIndex]){
                      maxIndex = i;
                  }
            }
            // 如果最大值是left下标，在交换后，left下标不是最大值下标了
              swap(array,minIndex,left);
            if(left ==maxIndex){
                maxIndex =minIndex;
            }
              swap(array,maxIndex,right);
          left++;
          right--;
        }
}
/**
 * 堆排序
 * 进行从小到大排序，则创建大根堆，然后将最大根置于堆尾，再重新调整大根堆
 *
 */
public void  heapsort(int[] array){
          //创建大根堆
    createHeap(array);
       //将最大根于堆尾元素进行交换，然后重新调整堆为大根堆，
        int end = array.length-1;
        //循环次数为元素的个数-1
     while (end>0) {
         swap(array, 0, end);
         end--;
         //向下调整
         siftDown(array,0,end);

     }
}
private void createHeap(int []array){
            //创建大根堆的方法:
    int parent = (array.length-1-1)/2;
    while (parent>=0){
        siftDown(array,parent,array.length-1);
        parent--;
    }
}
private void siftDown(int []array,int parent,int end){
    //要对单个堆进行向下调整
    int childleft = (parent*2)+1;
    int childright = (parent*2)+2;
    //获取左右孩子的最大值，
    // 左孩子不存在，右孩子也不会存在
    //当左孩子存在时，
    if(childleft<=end){
        //如果右孩子存在
        if(childright<=end&&array[childleft]<array[childright]){
            childleft = childright;
        }
        //比较左孩子的值与根节点的值
        if(array[childleft]>array[parent]){
            swap(array,childleft,parent);
        }
        siftDown(array,childleft,end);
    }
}
/**
 * 冒号排序
 */
public void  bubblesort(int[] array){
      //冒号排序每次比较出一个最大的值
    for (int i = 0; i <array.length-1 ; i++) {
        //对冒号排序进行优化，在冒号排序过程中，有可能一轮比较已经达到有序
        boolean fig = true;
        for (int j = 0; j < array.length-i-1; j++) {
            if(array[j]>array[j+1]){
                swap(array,j,j+1);
                fig =false;
            }
        }
        if(fig ==true){
            break;
        }
    }
}
/**
 * 快速排序
 * //采用挖坑法
 *
 */
public void quicksort(int []array){
      quickwakeng(array,0,array.length-1);
    //quickhore(array,0,array.length-1);
}
private void quickwakeng(int []array,int start,int end) {
    if (start >= end) {
        return;
    }
    int starttmp = start;
    int tmp = array[start];
    while (start < end) {
        while (array[end] >= tmp && start < end) {
            end--;
        }
        //可以用当前start与end标记当前停止指向的位置，来表示空位置
        array[start] = array[end];
        //此时end所指向的空间为空，
        while (array[start] <= tmp && start < end) {
            start++;
        }
        array[end] = array[start];
    }
        array[start]  =  tmp ;
      quickwakeng(array,starttmp,start-1);  //start的值一定为0吗？不一定
      quickwakeng(array,start+1,array.length-1); //end的值不一定为array.length-1,但是递归时，end不会局限array.lenth-1

}
//hore法
    private void quickhore(int []array,int start,int end){
    if(start>=end){
        return;
    }
    //确定基准值
           int tmpleft  = start;

       while (start<end){
             //先走右边的指标
            while (array[end]>=array[tmpleft]&&start<end){
                   end--;
            }
           //此时找到end指向小于基准值的值
           while (array[start]<=array[tmpleft]&&start<end){
               start++;
           }
           //此时找到start标记指向的大于基准值的值
           swap(array,start,end);
        //如果start等于end时，此时交换不会出现错误。
       }
        //当start等于end时：交换当前值与基准值
        swap(array,tmpleft,start);
       quickhore(array,tmpleft,start-1);
       quickhore(array,start+1,array.length-1);
    }
    //快速排序的优化：
    //快速排序在排序有序与逆序数据时，时间复杂度达到O(N^2)




    //快速排序：前后指针法：




/**
 *归并排序(递归实现)
 *
 */
     public  void  incorporateSort(int []array){
          //递归实现归并排序
         //recursionincorporate(array,0,array.length-1);
         //非递归实现归并排序
         no_recursionincorporate(array);
     }
     private void recursionincorporate(int []array,int left,int right){
         //如果划分的数组宽度只有一个元素大小时，则返回
              if(left>=right){
                  return;
              }
              //获取中间下标
            int  mid = (left+right)/2;
              //划分数组
         recursionincorporate(array,left,mid);
         recursionincorporate(array,mid+1,right);
             //划分数组完成后：开始进行合并，进行直接插入排序,
           //这样岂不是多此一举，合并时不应该采用直接插入排序
              //insertRangeSort(array,left,right);
         merge(array,left,right,mid);
              //排序完成后，返回上一个函数
     }
private void insertRangeSort(int[]array,int left,int right) {
    for (int i = left + 1; i <= right; i++) {
        int tmp = array[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (tmp < array[j]) {
                array[j + 1] = array[j];
            } else {
                array[j + 1] = tmp;
                break;
            }
        }
        array[j + 1] = tmp;
    }
}
private void merge(int []array,int left,int right,int mid){
         //将有序的数据先存放到临时的数组中去
    int[] tmp = new int[right-left+1];
        //对指定区间内两组数据进行排序
    int s1 = left;
    int e1 = mid;
    int s2 = mid+1;
    int e2 = right;
    int k = 0;
    while (s1<=e1&&s2<=e2){
        if(array[s1]<=array[s2]){
            tmp[k++] = array[s1++];   //如何设置临时数组的下标？我们需要循环一次，便++的下标，设置即可
        }else {
            tmp[k++] = array[s2++];
        }
    }
   //当退出循环时，说明有一个数组已经赋值完毕
      while (s1<=e1){
          //此时说明s2传送完毕
          tmp[k++] = array[s1++];
      }
     while (s2<=e2){
         tmp[k++] = array[s2++];
     }
     //将所有的有序数据存储到临时数组中后
    //赋值给array数组
    // right是数组的下标范围，还不能表示临时数组中元素的个数。
       // for (int i = 0; i <=right; i++) {
        for (int i = 0; i <k; i++) {

            array[i+left] = tmp[i];
    }
}
//归并排序的非递归实现：
  private void no_recursionincorporate(int[] array){
         //循环遍历数组，根据不同的gap值来对分数组进行排序
      for (int gap = 1; gap <= array.length ; gap*=2) {
               //获取每一个分组的左下标与右下标与中间下标
          for (int i = 0; i+gap < array.length-1; i+=gap) {
                 int right = i+gap-1;
                 int mid =  (right+i )/2;
                 merge(array,i,right,mid);
          }
      }
    }
//计数排序：














}






